#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        if k == 0:
            return None

        self.cur = 1
        self.k = k
        find, val = self.travel(pRoot)
        return val

    def travel(self, node):
        if node is None:
            return False, None

        find, v = self.travel(node.left)
        if find:
            return find, v

        if self.cur == self.k:
            # return True, node.val
            # 注意这里要返回节点, 而不是值
            return True, node

        self.cur += 1

        find, v = self.travel(node.right)
        return find, v
        # if find:
        #     return find, v

        # return False, None


def test():
    s = Solution()

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
